package leetcode.violence;

public class minPathSum1 {
    public static void main(String[] args) {
        int[][] arr = {{1,4,9,18},{9,5,8,12},{14,5,11,12},{22,13,15,12}};
        System.out.println( process(arr,0,0,0));
    }
    public static int process(int[][] arr,int n,int m,int aim){
        if (n==arr.length-1 && m==arr.length-1){
            return arr[n][m];
        }
        int p1 = 0;
        int p2 = 0;
        if (n==arr.length-1){
            p1=aim+process(arr,n,m+1,aim);
            return Math.max(p1,p2);
        }
        if (m==arr.length-1){
            p2=aim+process(arr,n+1,m,aim);
            return Math.max(p1,p2);
        }
        p1=aim+process(arr,n,m+1,aim);
        p2=aim=process(arr,n+1,m,aim);
        return Math.max(p1,p2);
    }

    public static int process(int[][] arr){
        if (arr == null || arr.length == 0 || arr[0]==null || arr[0].length ==0){
            return 0;
        }
        int row = arr.length;
        int col = arr[0].length;
        int[][] dp = new int[row][col];
        dp[0][0]=arr[0][0];
        for (int i = 1; i <row ; i++) {
            dp[i][0]=dp[i-1][0]+arr[i][0];
        }
        for (int i = 1; i <col ; i++) {
            dp[0][i]=dp[0][i-1]+dp[0][i];
        }
        for (int i = 1; i <row ; i++) {
            for (int j = 0; j <col ; j++) {
                dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+arr[i][j];
            }
        }
        return dp[row-1][col-1];
    }
}
